// -----------------------------
// projects/collatz/Collatz.java
// Copyright (C) 2010dd
// Glenn P. Downing
// -----------------------------

final class Collatz {

        final static int size = 10001;
        static int [] cache = new int [size];

    // ----
    // read
    // ----

    /**
     * reads an int into a[0] and a[1]
     * @return true if that succeeds, false otherwise
     */
    public static boolean read (Reader r, int[] a) {
        if (!r.hasNextInt())
            return false;
        a[0] = r.nextInt();
        a[1] = r.nextInt();
        assert a[0] > 0;
        assert a[1] > 0;
        return true;}


        /**
         *  computes the cycle length of a number
         *      @return cycle
         */
        public static int cycLen (int n){
                int cycle = 1;
                
                while (n != 1){
                        if (n % 2 == 0){
                                n = n/2;
                                ++cycle;
                        }
                        else{
                                assert n%2 == 1;
                                n = n+ (n >> 1) + 1;
                                cycle = cycle +2;
                        }               
                }
                return cycle;
        }

        private static int cacheCycLen(int n){
                if (n == 1){
					cache[n] = 1;
					return 1;
				}
				else if (n< size && cache [n] != 0){
					assert n < size && n > 1;
					return cache[n];
				}
				else if (n < size ){
					if (n %2 ==0){
						cache[n] = 1 + cacheCycLen (n/2);
						return cache[n];
					}
					else{
						cache[n] = 2 + cacheCycLen ((n+(n>>1) + 1));
						return cache[n];
					}
				}
				else{
					assert n >= size;
					
					if (n % 2 ==0)
						return 1 + cacheCycLen(n/2);
					else
						return 2 + cacheCycLen((n+(n>>1) + 1));
				} 	
							
        }

        private static int myMax(int [] a, int l, int u){
                int max = 0;
                for (int i = l; i <= u; ++i){
                        if (a[i] > max)
                                max = a[i];
                }
                return max;
        }       
        
    // ----
    // eval
    // ----

    /**
     * computes the max cycle length in the range [i, j]
     * and stores the result in v
     */
    public static int eval (int[] a) {

        assert a[0] > 0;
        assert a[1] > 0;
        int upper = a[1];
        int lower = a[0];				
        int tmp;
		if (upper < lower){
			tmp = lower;
			lower = upper;
			upper = tmp;
		}
		assert upper>=lower;
		tmp = lower;
        int Max = 0;
        while (tmp < upper){
            cacheCycLen(tmp);
            ++tmp;
        }
        Max = myMax(cache, lower, upper);                
        return Max;
    }

    // -----
    // print
    // -----

    /**
     * prints the values of a[0], a[1], and v
     */
    public static void print (Writer w, int[] a, int v) {
        assert a[0] > 0;
        assert a[1] > 0;
        assert v    > 0;
        w.write(a[0] + " " + a[1] + " " + v);}

        public static void printa(int []a){
                System.out.print("\n[ ");
                for (int i = 0; i < 1000; ++i)
                        System.out.print(a[i] + ", " );
                System.out.print(" ]");
        }
}


